﻿//力扣：974. 和可被 K 整除的子数组
//https://leetcode.cn/problems/subarray-sums-divisible-by-k/description/


//方法一：暴力法
//时间复杂度O(n^2)
class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        int ret = 0;                            // 结果变量，用于存储符合条件的子数组个数
        int n = nums.size();                    // 获取数组的大小

        for (int i = 0; i < n; i++)             // 外层循环：枚举每个子数组的起始点
        {
            int sum = 0;                        // 累计和，初始化为0，每次内层循环开始时重置
            for (int j = i; j < n; j++)         // 内层循环：枚举以i为起始点的每个子数组
            {
                sum += nums[j];                 // 将当前元素添加到累计和中
                if (sum % k == 0)               // 检查累计和是否能被k整除
                {
                    ret++;                      // 满足条件则结果计数+1
                }
            }
        }

        return ret;                             // 返回最终符合条件的子数组个数
    }
};





//方法二：前缀和+哈希表
//时间复杂度O(n)
//前缀和的余数相同，则两个位置之间的子数组和一定能被 k 整除。哈希表 mp 记录每个余数出现的次数，实现线性时间的查找和更新。

//知识补充：
//1. 同余定理：
//      如果(a - b) % n == 0 ，那么我们可以得到⼀个结论： a % n == b % n 。⽤⽂字叙述就是，如果两个数相减的差能被 n 整除（没有余数），那么这两个数对 n 取模的结果相同。
//      例如：(26 - 2) % 12 == 0 ，那么 26 % 12 == 2 % 12 == 2 。

//2. c++ 中负数取模的结果，以及如何修正「负数取模」的结果：
//    a.c++ 中关于负数的取模运算，结果是「把负数当成正数，取模之后的结果加上⼀个负号」。
//        例如： - 1 % 3 = -(1 % 3) = -1
//    b.因为有负数，为了防⽌发⽣「出现负数」的结果，以(a % n + n) % n 的形式输出保证为正。
//        例如： - 1 % 3 = (-1 % 3 + 3) % 3 = 2

//防止负数的出现，可以使用公式：(a % n + n) % n


//算法原理：
//思路与 560. 和为 K 的⼦数组 这道题的思路相似。

//设 i 为数组中的任意位置，⽤ sum[i] 表⽰[0, i] 区间内所有元素的和。
//• 想知道有多少个「以 i 为结尾的可被 k 整除的⼦数组」，就要找到有多少个起始位置为 x1, x2, x3... 使得[x, i] 区间内的所有元素的和可被 k 整除。
//• 设[0, x - 1] 区间内所有元素之和等于 a ，[0, i] 区间内所有元素的和等于 b ，可得(b - a) % k == 0 。
//• 由同余定理可得，[0, x - 1] 区间与[0, i] 区间内的前缀和同余。于是问题就变成：
//• 找到在[0, i - 1] 区间内，有多少前缀和的余数等于 sum[i] % k 的即可。

//我们仅需⽤⼀个哈希表，⼀边求当前位置的前缀和，⼀边存下之前每⼀种前缀和出现的次数。
class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        int ret = 0;                            // 结果变量，用于存储符合条件的子数组个数
        int sum = 0;                            // 前缀和，用于存储当前的累计和
        unordered_map<int, int> mp;             // 哈希表用于存储前缀和的余数出现次数

        mp[0] = 1;                              // 初始化当前缀和刚好为0的余数出现次数为1
        for (auto x : nums)                     // 遍历数组
        {
            sum += x;                           // 累加当前元素到前缀和
            int temp = (k + sum % k) % k;       // 计算前缀和的余数，确保为正数 (模运算原理)

            if (mp.count(temp))                 // 检查当前余数是否存在于哈希表
            {
                ret += mp[temp];                // 若存在，则将对应计数添加到结果
            }

            mp[temp]++;                         // 更新哈希表，将当前余数出现次数+1
        }

        return ret;                             // 返回符合条件的子数组总数
    }
};